# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def generateTrees(self, n: int) -> list:
        return self.search(range(1, n + 1))

    def search(self, lists: list):
        res = []
        for index, num in enumerate(lists):
            for note1 in self.search(lists[:index]) or [None]:
                for note2 in self.search(lists[index+1:]) or [None]:
                    root = TreeNode(num)
                    root.left, root.right = note1, note2
                    res.append(root)
        return res


a = Solution()
print(len(a.generateTrees(4)))
